package 算法.leetcode.offer;

/**
 * @author lchenglong
 * @date 2022/4/22
 */
public class Offer16 {

    public static void main(String[] args) {
        Offer16 instance = new Offer16();
        double ans = instance.myPow(8.66731, 4);
        System.out.println(ans);
        System.out.println(10&1);
//        System.out.println(Math.ceil(Math.log(128)/Math.log(2)));
    }

    /**
     * 二分推导： x^n = x^{n/2} * x^{n/2} = (x^2)^{n/2}
     * 令 n/2n/2 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 "//" ）：
     *
     * 当 n为偶数： x^n = (x^2)^{n//2}
     * 当 n为奇数： x^n = x(x^2)^{n//2}，即会多出一项 x ；
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        if (n==0)return 1;
        if (x == 0)return 0;
        // 避免溢出
        long b = n;
        if (n<0){
            b = -b;
            x = 1/x;
        }
        double res = 1.0;
        while (b>0){
            // n % 2 = 1
            if ((b&1)==1)
                res *= x;
            x *=x;
            // 向下整除2
            b>>=1;
        }
        return res;
    }



}
